#pragma once

#include <iostream>
#include <vector>

/// <summary>
/// - 环形队列
/// - 不是线程安全
/// </summary>
/// <typeparam name="T"></typeparam>
template <typename T>
class CircularQueue
{
	int rear, front;
	int size;
	T* arr = nullptr;

	int _len = 0;
public:
	CircularQueue(int s)
	{
		size = s;
		arr = new T[s];

		clear();
	}

	~CircularQueue() {
		if (arr)
		{
			delete[]arr;
		}
	};

	bool enQueue(T value)
	{
		if ((front == 0 && rear == size - 1) ||
			((rear + 1) % size == front))
		{
			printf("\nQueue is Full");
			return false;
		}

		_len++;

		if (front == -1)
		{
			front = rear = 0;
			arr[rear] = value;
		}

		else if (rear == size - 1 && front != 0)
		{
			rear = 0;
			arr[rear] = value;
		}

		else
		{
			rear++;
			arr[rear] = value;
		}

		return true;
	};



	bool deQueue(T* val = nullptr) {

		if (front == -1)
		{
			printf("\nQueue is Empty");
			return false;
		}

		_len--;

		T data = arr[front];
		arr[front] = -1;
		if (front == rear)
		{
			front = -1;
			rear = -1;
		}
		else if (front == size - 1)
			front = 0;
		else
			front++;

		if (val)
		{
			*val = data;
		}
		

		return true;
	};

	void autoQueue(T value) {

		while (enQueue(value) == false)
		{
			deQueue();
		}
	};

	int len()
	{
		return _len;
	};

	std::vector<T> list()
	{
		std::vector<T> vals;

		if (front == -1)
		{
			return vals;
		}

		if (rear >= front)
		{
			for (int i = front; i <= rear; i++)
			{
				vals.push_back(arr[i]);
			}

		}
		else
		{
			for (int i = front; i < size; i++)
			{
				vals.push_back(arr[i]);
			}

			for (int i = 0; i <= rear; i++)
			{
				vals.push_back(arr[i]);
			}
		}

		return vals;
	}

	void clear() {
		front = rear = -1;
		_len = 0;
	};

	void displayQueue() {

		std::vector<T> ls = list();
		printf("\n displayQueue: ");
		for (size_t i = 0; i < ls.size(); i++)
		{
			printf("%d ", ls[i]);
		}
		printf("\n");
	};
};

//int main()
//{
//	CircularQueue<int> q(5);
//	q.autoQueue(14);
//	q.autoQueue(22);
//	q.autoQueue(13);
//	q.autoQueue(-6);
//
//	q.displayQueue();
//
//	q.autoQueue(9);
//	q.autoQueue(20);
//	q.autoQueue(5);
//
//	q.displayQueue();
//
//	q.autoQueue(20);
//
//	q.displayQueue();
//	return 0;
//}
